'''
链接：https://www.nowcoder.com/questionTerminal/6a296eb82cf844ca8539b57c23e6e9bf?toCommentId=1227413
来源：牛客网

使用大顶堆维护 k 大小的大顶堆每次小于堆顶元素就将删除堆顶元素将新元素放进去重新调整。使用了heapq的内置数据结构，
用了一个trick 因为默认是创建小顶堆，所以在添加元素的时候加个 负号就变成大顶堆了。
'''

import heapq


class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        high = len(tinput) - 1
        if k > (high+1):
            return []
        res = self.quickSort(tinput, 0, high)
        return res[:k]

    def quickSort(self, L, low, high):
        if low >= high:
            return L
        left, right = low, high
        key = L[left]
        while left < right:
            while left < right and L[right] >= key:
                right -= 1
            L[left] = L[right]
            while left < right and L[left] <= key:
                left += 1
            L[right] = L[left]
        L[left] = key
        self.quickSort(L, low, left - 1)
        self.quickSort(L, right + 1, high)
        return L

    def GetLeastNumbers_Solution1(self, tinput, k):
        if k > len(tinput) or k == 0: return []
        heap = []
        for num in tinput:
            if len(heap) < k:
                heapq.heappush(heap, -num)
            else:
                if -num > heap[0]:
                    heapq.heapreplace(heap, -num)
        return sorted(list(map(lambda x: x*-1, heap)))

# 调整堆
def adjust_heap(lists, i, size):
    lc = 2 * i + 1
    rc = 2 * i + 2
    max = i
    if i < (size/2):
        if lc < size and lists[lc] > lists[max]:
            max = lc
        if rc < size and lists[rc] > lists[max]:
            max = rc
        if max != i:
            lists[max], lists[i] = lists[i], lists[max]
            adjust_heap(lists, max, size)


s = Solution()
print(s.GetLeastNumbers_Solution1([4,5,1,6,2,7,3,8], 4))
